/**
 * 优化后的单链表实现
 * 
 * 主要改进：
 * 1. 使用虚拟头节点简化边界处理
 * 2. 添加size字段提高性能
 * 3. 移除不必要的实例变量current
 * 4. 改进边界条件检查
 * 5. 统一代码风格和命名规范
 * 
 * 时间复杂度分析：
 * - get(index): O(index)
 * - addAtHead(val): O(1)
 * - addAtTail(val): O(size)
 * - addAtIndex(index, val): O(index)
 * - deleteAtIndex(index): O(index)
 */
class OptimizedMyLinkedList {
    
    /**
     * 链表节点的内部类定义
     * 使用内部类可以更好地封装节点结构
     */
    private class ListNode {
        int val;           // 节点值
        ListNode next;     // 指向下一个节点的指针
        
        // 构造函数
        ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }
    
    private ListNode dummyHead;  // 虚拟头节点，简化边界处理
    private int size;            // 链表长度，提高性能
    
    /**
     * 构造函数：初始化空链表
     * 使用虚拟头节点的好处：
     * 1. 统一处理头部插入和删除操作
     * 2. 避免特殊处理空链表的情况
     * 3. 简化代码逻辑，减少bug
     */
    public OptimizedMyLinkedList() {
        dummyHead = new ListNode(0);  // 虚拟头节点，值可以是任意数
        size = 0;
    }
    
    /**
     * 获取链表中第index个节点的值（从0开始）
     * 
     * @param index 节点索引
     * @return 节点值，如果索引无效返回-1
     * 
     * 时间复杂度：O(index)
     * 空间复杂度：O(1)
     */
    public int get(int index) {
        // 边界检查：索引必须在有效范围内
        if (index < 0 || index >= size) {
            return -1;
        }
        
        // 从虚拟头节点的下一个节点开始遍历
        ListNode current = dummyHead.next;
        
        // 移动到目标位置
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        
        return current.val;
    }
    
    /**
     * 在链表头部添加节点
     * 
     * @param val 要添加的值
     * 
     * 时间复杂度：O(1)
     * 空间复杂度：O(1)
     */
    public void addAtHead(int val) {
        addAtIndex(0, val);  // 复用addAtIndex方法，减少代码重复
    }
    
    /**
     * 在链表尾部添加节点
     * 
     * @param val 要添加的值
     * 
     * 时间复杂度：O(size)
     * 空间复杂度：O(1)
     */
    public void addAtTail(int val) {
        addAtIndex(size, val);  // 复用addAtIndex方法
    }
    
    /**
     * 在链表的第index个位置插入值为val的节点
     * 
     * @param index 插入位置（从0开始）
     * @param val   要插入的值
     * 
     * 插入规则：
     * - 如果index等于链表长度，则在尾部插入
     * - 如果index大于链表长度，则不执行插入操作
     * - 如果index小于0，则在头部插入
     * 
     * 时间复杂度：O(index)
     * 空间复杂度：O(1)
     */
    public void addAtIndex(int index, int val) {
        // 如果索引大于链表长度，不执行插入
        if (index > size) {
            return;
        }
        
        // 如果索引小于0，在头部插入
        if (index < 0) {
            index = 0;
        }
        
        // 创建新节点
        ListNode newNode = new ListNode(val);
        
        // 找到插入位置的前一个节点
        ListNode prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        
        // 执行插入操作
        newNode.next = prev.next;
        prev.next = newNode;
        
        // 更新链表长度
        size++;
    }
    
    /**
     * 删除链表中第index个节点
     * 
     * @param index 要删除的节点索引（从0开始）
     * 
     * 时间复杂度：O(index)
     * 空间复杂度：O(1)
     */
    public void deleteAtIndex(int index) {
        // 边界检查：索引必须在有效范围内
        if (index < 0 || index >= size) {
            return;
        }
        
        // 找到要删除节点的前一个节点
        ListNode prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        
        // 执行删除操作：跳过要删除的节点
        prev.next = prev.next.next;
        
        // 更新链表长度
        size--;
    }
    
    /**
     * 获取链表长度
     * 
     * @return 链表中节点的数量
     * 
     * 时间复杂度：O(1)
     * 空间复杂度：O(1)
     */
    public int getSize() {
        return size;
    }
    
    /**
     * 检查链表是否为空
     * 
     * @return 如果链表为空返回true，否则返回false
     * 
     * 时间复杂度：O(1)
     * 空间复杂度：O(1)
     */
    public boolean isEmpty() {
        return size == 0;
    }
    
    /**
     * 打印链表内容（用于调试）
     * 
     * @return 链表的字符串表示
     */
    @Override
    public String toString() {
        if (size == 0) {
            return "[]";
        }
        
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        
        ListNode current = dummyHead.next;
        while (current != null) {
            sb.append(current.val);
            if (current.next != null) {
                sb.append(", ");
            }
            current = current.next;
        }
        
        sb.append("]");
        return sb.toString();
    }
}

/**
 * 使用示例和测试代码
 */
class LinkedListTest {
    public static void main(String[] args) {
        // 创建链表实例
        OptimizedMyLinkedList list = new OptimizedMyLinkedList();
        
        // 测试各种操作
        System.out.println("=== 链表操作测试 ===");
        
        // 测试在头部添加
        list.addAtHead(1);
        System.out.println("addAtHead(1): " + list.toString());
        
        // 测试在尾部添加
        list.addAtTail(3);
        System.out.println("addAtTail(3): " + list.toString());
        
        // 测试在指定位置插入
        list.addAtIndex(1, 2);
        System.out.println("addAtIndex(1, 2): " + list.toString());
        
        // 测试获取元素
        System.out.println("get(1): " + list.get(1));
        
        // 测试删除元素
        list.deleteAtIndex(1);
        System.out.println("deleteAtIndex(1): " + list.toString());
        
        // 测试链表长度
        System.out.println("链表长度: " + list.getSize());
        
        // 测试边界情况
        System.out.println("get(-1): " + list.get(-1));  // 应该返回-1
        System.out.println("get(10): " + list.get(10));  // 应该返回-1
    }
}